#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

char lookahead;
enum TERMINAL
{
    ID,
    ADD,
    MUL,
    LBR,
    RBR,
    END,
    ERR
};

enum NON_TERMINAL
{
    E,
    T,
    F
};

enum ACTION_TYPE
{
    SHIFT,
    REDUCE,
    ERROR,
    ACC
};

#define NUM_TERMINAL  6
#define NUM_NONTERMINAL  3
#define NUM_STATES  12

struct action
{
    enum ACTION_TYPE type;
    int id;
}  actionTable[NUM_STATES][NUM_TERMINAL];

int gotoTable[NUM_STATES][NUM_NONTERMINAL];

int stackPtr;
int stack[1024];
void push(int state)
{
    stack[stackPtr] = state;
    stackPtr ++;
}

void pop()
{
    stackPtr --;
}

int top()
{
    return stack[stackPtr - 1];
}

void init()
{
    int i, j;

    //stack
    stackPtr = 0;
    push(0);

    //action and goto tables
    for(i = 0; i < NUM_STATES; i ++)
    {
        for(j = 0; j < NUM_TERMINAL; j ++)
        {
            actionTable[i][j].type = ERROR;
        }
        for(j = 0; j < NUM_NONTERMINAL; j ++)
        {
            gotoTable[i][j] = -1;
        }
    }

    //fill in the goto table
    gotoTable[0][E] = 1;
    gotoTable[0][T] = 2;
    gotoTable[0][F] = 3;
    gotoTable[4][E]=8;
    gotoTable[4][T]=2;
    gotoTable[4][F]=3;
    gotoTable[6][T]=9;
    gotoTable[6][F]=3;
    gotoTable[7][F]=10;


    //fill in the action table
    actionTable[0][ID].type=SHIFT;
    actionTable[0][ID].id=5;
    actionTable[0][LBR].type=SHIFT;
    actionTable[0][LBR].id=4;
    actionTable[1][ADD].type=SHIFT;
    actionTable[1][ADD].id=6;
    actionTable[1][END].type=ACC;
    actionTable[2][ADD].type = REDUCE;
    actionTable[2][ADD].id = 2;
    actionTable[2][MUL].type = SHIFT;
    actionTable[2][MUL].id = 7;
    actionTable[2][RBR].type = REDUCE;
    actionTable[2][RBR].id = 2;
    actionTable[2][END].type = REDUCE;
    actionTable[2][END].id = 2;
    actionTable[3][ADD].type=REDUCE;
    actionTable[3][ADD].id=4;
    actionTable[3][MUL].type=REDUCE;
    actionTable[3][MUL].id=4;
    actionTable[3][RBR].type=REDUCE;
    actionTable[3][RBR].id=4;
    actionTable[3][END].type=REDUCE;
    actionTable[3][END].id=4;
    actionTable[4][ID].type=SHIFT;
    actionTable[4][ID].id=5;
    actionTable[4][LBR].type=SHIFT;
    actionTable[4][LBR].id=4;
    actionTable[5][ADD].type=REDUCE;
    actionTable[5][ADD].id=6;
    actionTable[5][MUL].type=REDUCE;
    actionTable[5][MUL].id=6;
    actionTable[5][RBR].type=REDUCE;
    actionTable[5][RBR].id=6;
    actionTable[5][END].type=REDUCE;
    actionTable[5][END].id=6;
    actionTable[6][ID].type=SHIFT;
    actionTable[6][ID].id=5;
    actionTable[6][LBR].type=SHIFT;
    actionTable[6][LBR].id=4;
    actionTable[7][ID].type=SHIFT;
    actionTable[7][ID].id=5;
    actionTable[7][LBR].type=SHIFT;
    actionTable[7][LBR].id=4;
    actionTable[8][ADD].type=SHIFT;
    actionTable[8][ADD].id=6;
    actionTable[8][RBR].type=SHIFT;
    actionTable[8][RBR].id=11;
    actionTable[9][ADD].type=REDUCE;
    actionTable[9][ADD].id=1;
    actionTable[9][MUL].type=SHIFT;
    actionTable[9][MUL].id=7;
    actionTable[9][RBR].type=REDUCE;
    actionTable[9][RBR].id=1;
    actionTable[9][END].type=REDUCE;
    actionTable[9][END].id=1;
    actionTable[10][ADD].type=REDUCE;
    actionTable[10][ADD].id=3;
    actionTable[10][MUL].type=REDUCE;
    actionTable[10][MUL].id=3;
    actionTable[10][RBR].type=REDUCE;
    actionTable[10][RBR].id=3;
    actionTable[10][END].type=REDUCE;
    actionTable[10][END].id=3;
    actionTable[11][ADD].type=REDUCE;
    actionTable[11][ADD].id=5;
    actionTable[11][MUL].type=REDUCE;
    actionTable[11][MUL].id=5;
    actionTable[11][RBR].type=REDUCE;
    actionTable[11][RBR].id=5;
    actionTable[11][END].type=REDUCE;
    actionTable[11][END].id=5;
}

enum TERMINAL lexical(FILE *fp)
{

    lookahead = getc(fp);

    while(lookahead == ' ' || lookahead == '\t' || lookahead == '\n')
    {
        lookahead = getc(fp);
    }

    if(isdigit(lookahead))
    {
        while(isdigit(lookahead))
        {
            lookahead = getc(fp);
        }
        ungetc(lookahead, fp);
        return ID;
    }
    else if (lookahead == '+')
    {
        return ADD;
    }
    else if (lookahead == '*')
    {
        return MUL;
    }
    else if(lookahead == EOF)
    {
        return END;
    }
    else if(lookahead == '(')
    {
        return LBR;
    }
    else if(lookahead == ')')
    {
        return RBR;
    }
    else
    {
        return ERR;
    }
}

void parse(enum TERMINAL *input)
{
    int currentState = 0;
    int index = 0;

    while(1)
    {
        printf("currentState: %d\n", currentState);
        switch(actionTable[currentState][input[index]].type)
        {
        case SHIFT:
            currentState=actionTable[currentState][input[index]].id;
            push(currentState);
            index++;
            break;
        case REDUCE:
            switch(actionTable[currentState][input[index]].id)
            {
            case 1:
                pop();
                pop();
                pop();
                push(gotoTable[top()][E]);
                currentState=top();
                break;
            case 2:
                pop();
                push(gotoTable[top()][E]);
                currentState=top();
                break;
            case 3:
                pop();
                pop();
                pop();
                push(gotoTable[top()][T]);
                currentState=top();
                break;
            case 4:
                pop();
                push(gotoTable[top()][T]);
                currentState=top();
                break;
            case 5:
                pop();
                pop();
                pop();
                push(gotoTable[top()][F]);
                currentState=top();
                break;
            case 6:
                pop();
                push(gotoTable[top()][F]);
                currentState=top();
                break;
            default:
                printf("ERROR REDUCE\n");
                exit(-1);
                break;
            }
            break;
        case ERROR:
            printf("ERROR ACTION\n");
            exit(-1);
            break;
        case ACC:
            if(input[index] == END)
            {
                printf("ACC\n");
                return;
            }
            else
            {
                printf("ERROR ACC\n");
                exit(-1);
            }
            break;
        }
    }
}


int main(int argc, char **argv)
{
    enum TERMINAL input[1024];
    int inputIndex = 0;
    FILE *fp;
    enum TERMINAL temp;
    if(argc < 2)
    {
        printf("insufficient arguments");
        return 1;
    }
    fp = fopen(argv[1], "r");
    while((temp = lexical(fp)) != END)
    {
        input[inputIndex++] = temp;
    }

    input[inputIndex] = END;
    fclose(fp);

    init();
    parse(input);

    return 0;
}

